#include <iostream>
#include <string>
using  namespace std;

class Solution {
public:
    string get_new_string(string &s) {
        string ns = "#";
        for (int i = 0; s[i]; i++) {
            (ns += s[i]) += "#";
        }
        return ns;
    }

    string longestPalindrome(string s) {
        if (s.size() == 0) return "";

        string ns = get_new_string(s);
        std::vector<int> dis(ns.size()); // dis数组存该点的最长回文串的长度

        int l = 0, r = -1;
        for (int i = 0; i < ns.size(); i++) {
            if (i > r) {
                dis[i] = 1;
            } else {
                dis[i] = min(dis[l + r - i], r - i);
            }

            // 朴素的回文串判断办法
            while (i - dis[i] > 0 && ns[i - dis[i] == ns[i + dis[i]]) {
                dis[i]++;
            }
        }
    }
};

int main() {
    Solution leetcode;
    cout << leetcode.longestPalindrome("babad");

    return 0;
}